#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;

void InsertSort(int* a, int n)
{
	for (int i = 0; i < n-1; i++)
	{
		int end = i;
		int tmp = a[i+1];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}
void Hore(int* a, int n)
{
	int grep = n;
	while (grep > 1)
	{
		grep /= 3 + 1;
		for (int i = 0; i < n - grep; i++)
		{
			int end = i;
			int tmp = a[i + grep];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + grep] = a[end];
					end-=grep;
				}
				else
				{
					break;
				}
			}
			a[end + grep] = tmp;
		}
	}
	
}
int main()
{
	int a[] = { 2,1,8,5,9 };
	//InsertSort(a, sizeof(a) / sizeof(a[0]));
	Hore(a, sizeof(a) / sizeof(a[0]));

	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		cout << a[i] << " ";
	}

	return 0;
}